Aprendizado de Máquina I

Hugo Tremonte de Carvalho

hugo@dme.ufrj.br


05 - Métodos não-paramétricos: Árvores de regressão

Árvores de regressão

Visão geral

  • Resultados muito interpretáveis
  • Particionamento recursivo do espaço das covariáveis
  • Imita, muito vagamente, processos cognitivos de tomadas de decisão
  • Lidam bem com covariáveis qualitativas e quantitativas
  • Proder preditivo usualmente menor que o de outros métodos
  • Usualmente são não robustas: uma pequena mudança nos dados pode levar a estimativas muito discrepantes
    • Tentaremos contornar esses problemas

Um exemplo

Figura 4.6 de [AME]

Um exemplo mais concreto

Figura 4.7 de [AME]: Regressão do salário de um indivíduo dadas as covariáveis idade e anos de estudo.

Formalizando

  • Partição do espaço das covariáveis
    • Regiões \(R_1, \dots, R_j\) distintas disjuntas
    • A predição para a resposta \(Y\) de uma observação \(\mathbf{x}\) que está na região \(k\) é a média das respostas cujos respectivos \(\mathbf{x}\) também estão nessa região: \[g(\mathbf{x}) = \frac{1}{\#\{i ~ | ~ \mathbf{x}_i \in R_k\}} \sum_{i ~ | ~ \mathbf{x}_i \in R_k} y_i.\]

Formalizando

  • Criação em duas etapas:
    1. Criação de uma árvore “completa” e “complexa”
      • Árvores puras
      • Partições onde os valores de \(Y\) no conjunto de treinamento em cada folha sejam “homogêneos”
    2. Poda da árvore para evitar sobreajuste
      • Reduzir a complexidade da árvore
      • Remover nós “desnecessários”

Etapa 1: Criação da árvore

  • Medida de plausibilidade de uma árvore \(T\): erro quadrático médio: \[\mathcal{P}(T) = \frac{1}{n} \sum_R \sum_{i ~ | ~ \mathbf{x}_i \in R} (y_i - \widehat{y}_R)^2\]
  • \(\widehat{y}_R\): valor predito para a resposta de uma observação em \(R\)
  • \(\displaystyle \mathrm{arg}\min_T \mathcal{P}(T)\) \(\Rightarrow\) estudar todas as partições! Inviável
  • Heurística simplificadora: divisão binária recursiva

Etapa 1: Criação da árvore

Figura 8.3 de [ITSL]: Particionamento proveniente de divisão binária recursiva (direita) e particionamento mais geral (esquerda)

Etapa 1: Criação da árvore

  • Particionar o espaço de covariáveis em duas regiões
    • Busca de covariável \(x_i\) e corte \(t_1\)
    • Partição \((R_1, R_2)\) com predições de menor EQM: \[\sum_{i ~ | ~ \mathbf{x}_i \in R_1} (y_i - \widehat{y}_{R_1})^2 + \sum_{i ~ | ~ \mathbf{x}_i \in R_2} (y_i - \widehat{y}_{R_2})^2\]
    • \(R_1 = \{\mathbf{x} ~ | ~ x_i < t_1\}\) e \(R_2 = \{\mathbf{x} ~ | ~ x_i \geq t_1\}\)

Etapa 1: Criação da árvore

Figura 4.8 de [AME]: a) Onde chegamos com o passo-a-passo anterior; b) onde queremos chegar no próximo passo

  • Nó inicial fixado
  • Particionar \(R_1\) ou \(R_2\) em regiões menores
  • Repetir a estratégia

Etapa 1: Criação da árvore

  • Particionar \(R_1\) ou \(R_2\) em regiões menores
    • Busca de covariável \(x_j\) e corte \(t_2\)
    • Decidir qual região particionar, \(R_1\) ou \(R_2\)
    • Sempre para minimizar o EQM
  • Assumindo escolhida a região \(R_1\), temos: \[R_{1,1} = \{\mathbf{x} ~ | ~ x_i < t_1, x_j < t_2\}\] \[R_{1,2} = \{\mathbf{x} ~ | ~ x_i < t_1, x_j \geq t_2\}\] \[R_2 = \{\mathbf{x} ~ | ~ x_i \geq t_1\}\]

Etapa 1: Criação da árvore

Figura 4.8 de [AME]: b) Onde chegamos com o passo-a-passo anterior; c) d) continuações hipotéticas do processo

  • Continuar até cada folha ter “poucas” observações

Etapa 1: Criação da árvore

Figura 8.3 de [ITSL]: Árvore (esquerda) e gráfico da função \(g\) correspondente (direita)

Um exemplo até aqui

\(X \sim \mathcal{U}[0, 4]\)

\(f(x) = \sin(\pi x)\)

\(Y = f(X) + \varepsilon\)

\(\varepsilon \sim \mathcal{N}(0, 0.4)\)

Um exemplo até aqui

scikit-learn - DecisionTreeRegressor

DTR = DecisionTreeRegressor(max_depth = None, min_samples_leaf = 5)
DTR.fit(x_tr.reshape(-1, 1), y_tr)
print('ATENÇÃO: Diversos hiperparâmetros para ajustar!')
ATENÇÃO: Diversos hiperparâmetros para ajustar!

Um exemplo até aqui

Visualizando (ou tentando visualizar…) a árvore

plt.figure(figsize=(12,20)) 
plot_tree(DTR, fontsize=10)
plt.show()

Etapa 2: Poda da árvore

  • Retirar nós da árvore para melhorar sua capacidade preditiva
    • Como escolher os nós a serem removidos?
  • Poda por custo de complexidade
    • Ideia reminiscente do Lasso
    • Árvore “grande” \(T\) e hiperparâmetro \(\alpha\)
    • Sub-árvore \(T_{\alpha} \subset T\) que minimiza \[\sum_{m = 1}^{|T_{\alpha}|} \sum_{i ~ | ~ \mathbf{x}_i \in R_m} (y_i - \widehat{y}_{R_m})^2 + \alpha |T_{\alpha}|\]

Etapa 2: Poda da árvore

  • Sub-árvore \(T_{\alpha} \subset T\) que minimiza \[\sum_{m = 1}^{|T_{\alpha}|} \sum_{i ~ | ~ \mathbf{x}_i \in R_m} (y_i - \widehat{y}_{R_m})^2 + \alpha |T_{\alpha}|\]
    • \(|T_{\alpha}|\): número de nós terminais da árvore
    • \(R_m\): região correspondente ao \(m\)-ésimo nó terminal
  • \(\alpha\) controla equilíbrio entre complexidade e ajuste aos dados (encontrado por validação cruzada)
  • Poda diminui variância mas aumenta o viés

Continuando no exemplo

DTR = DecisionTreeRegressor(max_depth = None, min_samples_leaf = 5,
                            ccp_alpha = 0.01)
DTR.fit(x_tr.reshape(-1, 1), y_tr);

Visualizando a árvore

plt.figure(figsize=(12,20)) 
plot_tree(DTR, fontsize=10)
plt.show()

Escolhendo \(\alpha\) por validação cruzada

DTR = DecisionTreeRegressor(max_depth = None, min_samples_leaf = 5)
param_grid_DTR = {"ccp_alpha": [0.0001, 0.0001, 0.001, 0.01, 0.03, 0.05, 0.07, 0.1, 0.2]}
DTRCV = GridSearchCV(DTR, param_grid = param_grid_DTR, scoring='neg_mean_squared_error', cv = 5)

DTRCV.fit(x_tr.reshape(-1, 1), y_tr)
print(DTRCV.best_estimator_)
DecisionTreeRegressor(ccp_alpha=0.01, min_samples_leaf=5)

Visualizando a árvore podada

Árvores vs. modelos lineares

  • Modelos lineares: \(\displaystyle g(\mathbf{x}) = \beta_0 + \sum_{i = 1}^{p} \beta_i x_i\)
  • Árvores: \(\displaystyle g(\mathbf{x}) = \sum_{m = 1}^{M} c_m \mathbb{I}_{R_m}(\mathbf{x})\)
    • \(\mathbb{I}_A\) função indicadora do conjunto \(A\)
    • \(R_1, \dots, R_M\) partição do espaço de covariáveis
    • Mais adequada para capturar relações não-lineares entre as covariáveis e a resposta

Bagging e Florestas Aleatórias

Uma floresta aleatória… 🙂

Visão de ambos os métodos

  • Agregar \(B\) árvores para melhorar o poder preditivo
  • Bagging
    • Gerar árvores através de amostras bootstrap dos dados
    • Funciona para outros modelos, não somente árvores
  • Florestas aleatórias
    • Gerar árvores através de amostras bootstrap dos dados
    • Crescer a árvore com “mais cuidado”

Bagging

  • Contexto de regressão, duas funções de predição: \(g_1\) e \(g_2\)
    • Riscos condicionados em \(\mathbf{x}\) mas não na amostra de treinamento \(\Rightarrow\) \(\mathbb{E} = \mathbb{E}_{\mathcal{D}, Y}\) \[\mathbb{E}\left[ \left. \left(Y - g_1(\mathbf{x})\right)^2 \right| \mathbf{x} \right] \quad \text{e} \quad \mathbb{E}\left[ \left. \left(Y - g_2(\mathbf{x})\right)^2 \right| \mathbf{x} \right]\]
    • Estimador combinado \(\displaystyle g(\mathbf{x}) = \frac{g_1(\mathbf{x}) + g_2(\mathbf{x})}{2}\)
    • Sob certas hipóteses: \(\displaystyle \mathbb{E}\left[ \left. \left(Y - g(\mathbf{x})\right)^2 \right| \mathbf{x} \right] \leq \mathbb{E}\left[ \left. \left(Y - g_i(\mathbf{x})\right)^2 \right| \mathbf{x} \right], i = 1, 2\)

Bagging

  • Generalizar para \(B\) funções de predição: \[g(\mathbf{x}) = \frac{1}{B} \sum_{b = 1}^{B} g_b(\mathbf{x})\]
    • \(g_b\) geradas através de amostras bootstrap
      • \(\mathbf{x}_1, \dots, \mathbf{x}_n\) conjunto de treinamento
      • \(\mathbf{x}_{i_1}, \dots, \mathbf{x}_{i_n}\) amostras com reposição do conjunto de treinamento \(\Rightarrow\) amostra bootstrap
      • Usar esse conjunto para estimar \(g_b\)

Bagging - atenção!

  • As \(g_b\) precisam ser não-viesadas \(\Rightarrow\) não podar as árvores!
  • As \(g_b\) precisam ser descorrelacionadas \(\Rightarrow\) isso é um problema, na verdade…
    • Florestas aleatórias tentam resolvê-lo
    • Mas vejamos uma coisa de cada vez!

Um exemplo

scikit-learn - BaggingRegressor

DTB = BaggingRegressor(estimator = DecisionTreeRegressor(max_depth = None, min_samples_leaf = 5), n_estimators = 1000)
print('ATENÇÃO: Diversos hiperparâmetros para ficar atento/a!')
ATENÇÃO: Diversos hiperparâmetros para ficar atento/a!

Fechando o bagging

  • Menos interpretável que árvores de regressão
  • Potencialmente maior poder preditivo
  • Permite criar uma medida de importância para cada covariável

Medindo a importância dos atributos

Figura 4.10 de [AME] Divisão de um nó de uma árvore usado para ilustrar o cálculo do RSS
  • Baseada na redução da soma de quadrados dos resíduos de cada divisão (RSS - residual sum of squares)
  • RSS referente à divisão da figura: \[\begin{align*} &\mathrm{RSS}_{\mathrm{pai}} - \mathrm{RSS}_{\mathrm{esq}} - \mathrm{RSS}_{\mathrm{dir}} \\ &\sum_{i \in \mathrm{pai}} \left(y_i - \widehat{y}_{\mathrm{pai}}\right)^2 - \sum_{i \in \mathrm{esq}} \left(y_i - \widehat{y}_{\mathrm{esq}}\right)^2 \\ &- \sum_{i \in \mathrm{dir}} \left(y_i - \widehat{y}_{\mathrm{dir}}\right)^2\end{align*}\]

Medindo a importância dos atributos

  • Primeiramente, calcula-se o RSS para todos os nós gerados com base em determinado atributo
  • Repete-se para todas as árvores
  • Calcula-se a média dessa redução \(\Rightarrow\) medida de importância do atributo
  • Específico de árvores \(\Rightarrow\) não está implementado em BaggingRegressor no scikit-learn
  • Está implementado em DecisionTreeRegressor, RandomForestRegressor e seus equivalentes para classificação (atributo feature_importances_)

Um exemplo

scikit-learn - make_regression

X, y = make_regression(n_samples = 1000, n_features = 100,
                       n_informative = 10, n_targets = 1, noise = 1)
DT_importance = RandomForestRegressor(n_estimators = 100, max_depth = None,
                                      min_samples_leaf = 5, max_features = None)
print('Florestas aleatórias com \'max_features = None\' é equivalente ao bagging!')
print('Vamos ver florestas aleatórias logo a seguir')
Florestas aleatórias com 'max_features = None' é equivalente ao bagging!
Vamos ver florestas aleatórias logo a seguir

Florestas aleatórias

  • Bagging
    • \(g_b\) construídos a partir de amostras bootstrap
    • Estimadores correlacionados!
  • Florestas aleatórias visam diminuir essa correlação
    • Criar um novo nó da árvore
    • Escolher não mais uma dentre as \(p\) covariáveis
    • Escolher uma dentre \(m < p\)
    • \(m\) candidatas escolhidas aleatoriamente
    • \(m \approx p/3\) ou \(\sqrt{p}\) leva a bons resultados

Um exemplo

scikit-learn - RandomForestRegressor

RF = RandomForestRegressor(n_estimators = 1000, max_depth = None, min_samples_leaf = 5, max_features = 'log2')
print('ATENÇÃO: Diversos hiperparâmetros para ficar atento/a!')
print('SÓ TEMOS UM ATRIBUTO!!!! É equivalente ao bagging.')
ATENÇÃO: Diversos hiperparâmetros para ficar atento/a!
SÓ TEMOS UM ATRIBUTO!!!! É equivalente ao bagging.